package MargeSort;

/*
*       归并排序，是对于分治法的一个典型的应用。
*       核心思想是，将需要排序的元素进行分段，之后将分段后的子序列进行合并，最终得到完全有序的序列
*
*       具体的算法步骤比较复杂：
*       1. 如果只是输入一个元素，则直接返回，否则将长度为 n 的输入序列分为两个长度为 n/2
*       2. 分别对于两个子序列间归并排序操作，知道两个子序列变为有序状态
*       3. 设定两个指针分别指向两个已经排序子序列的起始位置
*       4. 比较两个指针指向的元素，选择相对较小的存放到合并空间，并且移动指针到下一位置
*       5. 重复上述步骤，直到某一个指针移动到序列尾部
*       6. 将另一序列进行复制合并
 */


import java.util.Arrays;

public class Marge {

    public static int[] margeSort (int[] arr) {
        // 当这里数组中的值小于 1 时，此时不需要进行排序操作，直接返回数据元素即可
        if(arr.length <= 1) {
            return arr;
        }

        // 需要找到中间值来对数据进行分割
        int mid = arr.length / 2;
        // 将数组拆解成两部分，分别的将两部分数据存入单独的排序空间进行排序操作
        int[] arr1 = Arrays.copyOfRange(arr, 0, mid);
        int[] arr2 = Arrays.copyOfRange(arr , mid, arr.length);
        // 通过核心的排序算法，将被分割的数组进行排序操作
        // 不断的进行递归对数组进行拆分的操作，以此来实现对数组的划分最后划分到元素的最小单位。
        return sort(margeSort(arr1), margeSort(arr2));
    }

    // 这里实现的是核心的排序操作
    public static int[] sort(int[] arr1, int[] arr2) {
        // 首先定义一个新的数组提供额外空间，主要用来存储排序好的两个数组元素
        int[] sort_arr = new int[arr1.length + arr2.length];
        // 这里需要定义三个指针
        int index  = 0;     // 记录 sort_arr 下标
        int index1 = 0;     // 记录 arr1 的下标
        int index2 = 0;     // 记录 arr2 的下标

        // 首先进行一轮大范围循环判断当前 arr1 和 arr2 数组中的元素大小
        while(index1 < arr1.length && index2 < arr2.length) {
            // 针对两个数组中的元素进行比较，找到其中较小的值存储到当前 sort_arr 数组中
            if(arr1[index1] < arr2[index2]) {
                sort_arr[index] = arr1[index1];
                // 存储结束后让 index1++
                index1++;
            } else {
                sort_arr[index] = arr2[index2];
                // 添加完 arr2 中的元素后让 index2++
                index2++;
            }
            // 进行一轮判断后，让临时数组的指针进行自增
            index++;
        }
        // 在上面的元素添加完成后，对于两个数组需要进行剩余判断
        // 哪一个数组有剩余，就将哪一个数组中剩余的元素存储到 sort_arr 数组中
        if(index1 < arr1.length) {
            // 将剩余的元素全部添加到 sort_arr 数组中
            while(index1 < arr1.length) {
                sort_arr[index] = arr1[index1];
                index++;
                index1++;
            }
        } else {
            // 同样的也要针对 arr2 数组进行一波判断
            while(index2 < arr2.length) {
                sort_arr[index] = arr2[index2];
                index++;
                index2++;
            }
        }
        // 之后将排序好的数组进行返回
        return sort_arr;
    }

    public static void main(String[] args) {
        int[] arr = {9,8,6,5,4,7,2,1,3,0};

        int re[] = margeSort(arr);
        System.out.println(Arrays.toString(re));
    }
}
